/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-05-26
 * Time: 19:02
 */
public class MaxProfit_2 {
    //动态规划
    public int maxProfit1(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }

    //贪心:由于可以进⾏⽆限次交易，所以只要是⼀个「上升区域」，我们就把利润拿到⼿就好了
    public int maxProfit2(int[] prices) {
        int ret = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                ret += prices[i] - prices[i - 1];
            }
        }
        return ret;
    }
    public int maxProfit3(int[] prices)
    {
        // 实现⽅式⼀：双指针
        int ret = 0, n = prices.length;
        for(int i = 0; i < n; i++)
        {
            int j = i;
            while(j + 1 < n && prices[j] < prices[j + 1]) j++; // 向后寻找上升的末端
            ret += prices[j] - prices[i];
            i = j;
        }
        return ret;
    }
}
